home *** CD-ROM | disk | FTP | other *** search
/ Over 1,000 Windows 95 Programs / Over 1000 Windows 95 Programs (Microforum) (Disc 1).iso / 0361 / qs.bas < prev    next >
BASIC Source File  |  1997-03-31  |  3KB  |  95 lines
  1. DefInt A-Z
  2.  
  3. 'This code from the VBDOS sample sort application
  4. '
  5. ' ============================== QuickSort ===================================
  6. '   QuickSort works by picking a random "pivot" element in SortArray, then
  7. '   moving every element that is bigger to one side of the pivot, and every
  8. '   element that is smaller to the other side.  QuickSort is then called
  9. '   recursively with the two subdivisions created by the pivot.  Once the
  10. '   number of elements in a subdivision reaches two, the recursive calls end
  11. '   and the array is sorted.
  12. ' ============================================================================
  13. '
  14. Sub QuickSort (Low, High)
  15.    If Low < High Then
  16.  
  17.       ' Only two elements in this subdivision; swap them if they are out of
  18.       ' order, then end recursive calls:
  19.       If High - Low = 1 Then
  20.          If TaskList(Low).WTitle$ > TaskList(High).WTitle$ Then
  21.             T$ = TaskList(Low).WTitle
  22.             TH = TaskList(Low).HWnd
  23.             TaskList(Low).WTitle = TaskList(High).WTitle
  24.             TaskList(Low).HWnd = TaskList(High).HWnd
  25.             TaskList(High).WTitle = T$
  26.             TaskList(High).HWnd = TH
  27.          End If
  28.       Else
  29.  
  30.          ' Pick a pivot element at random, then move it to the end:
  31.          RandIndex = RandInt%(Low, High)
  32.          'SWAP TaskList$(High), TaskList$(RandIndex)
  33.          T$ = TaskList(RandIndex).WTitle
  34.          TH = TaskList(RandIndex).HWnd
  35.          TaskList(RandIndex).WTitle = TaskList(High).WTitle
  36.          TaskList(RandIndex).HWnd = TaskList(High).HWnd
  37.          TaskList(High).WTitle = T$
  38.          TaskList(High).HWnd = TH
  39.          mPartition$ = TaskList(High).WTitle
  40.          Do
  41.  
  42.             ' Move in from both sides towards the pivot element:
  43.             I = Low: J = High
  44.             Do While (I < J) And (TaskList(I).WTitle <= mPartition$)
  45.                I = I + 1
  46.             Loop
  47.             Do While (J > I) And (TaskList(J).WTitle >= mPartition$)
  48.                J = J - 1
  49.             Loop
  50.  
  51.             ' If we haven't reached the pivot element, it means that two
  52.             ' elements on either side are out of order, so swap them:
  53.             If I < J Then
  54.                'SWAP TaskList$(I), TaskList$(J)
  55.                T$ = TaskList(I).WTitle
  56.                TH = TaskList(I).HWnd
  57.                TaskList(I).WTitle = TaskList(J).WTitle
  58.                TaskList(I).HWnd = TaskList(J).HWnd
  59.                TaskList(J).WTitle = T$
  60.                TaskList(J).HWnd = TH
  61.             End If
  62.          Loop While I < J
  63.  
  64.          ' Move the pivot element back to its proper place in the array:
  65.          'SWAP TaskList$(I), TaskList$(High)
  66.          T$ = TaskList(I).WTitle
  67.          TH = TaskList(I).HWnd
  68.          TaskList(I).WTitle = TaskList(High).WTitle
  69.          TaskList(I).HWnd = TaskList(High).HWnd
  70.          TaskList(High).WTitle = T$
  71.          TaskList(High).HWnd = TH
  72.  
  73.          ' Recursively call the QuickSort procedure (pass the smaller
  74.          ' subdivision first to use less stack space):
  75.          If (I - Low) < (High - I) Then
  76.             QuickSort Low, I - 1
  77.             QuickSort I + 1, High
  78.          Else
  79.             QuickSort I + 1, High
  80.             QuickSort Low, I - 1
  81.          End If
  82.       End If
  83.    End If
  84. End Sub
  85.  
  86. ' =============================== RandInt% ===================================
  87. '   Returns a random integer greater than or equal to the Lower parameter
  88. '   and less than or equal to the Upper parameter.
  89. ' ============================================================================
  90. '
  91. Static Function RandInt% (lower, Upper)
  92.    RandInt% = Int(Rnd * (Upper - lower + 1)) + lower
  93. End Function
  94.  
  95.